In computer vision, segmentation refers to the process of partitioning a digital image into multiple regions, i.e., disjoint sets of pixels. The goal of the segmentation is to simplify and/or change the representation of the image into something that is more meaningful and easier to analyze. Segmentation is typically used to locate objects and boundaries in images. The result of image segmentation is a set of regions, or a set of contours extracted from the image.
However, automatic segmentation of an object in an image is challenging in the presence of image noise, background clutter and occlusions. In semi-automatic segmentation, a user specifies a region of interest (ROI), and segmentation methods are applied such that a countour that best fits the object in ROI in the image is determined.
A random walk (RW) is a mathematical formalization of a trajectory that includes taking successive random steps. Specific cases or limits of random walks include the drunkard's walk and Lévy flight. Random walks are related to diffusion models and are a fundamental topic in discussions of Markov processes. Properties of random walks, including dispersal distributions, first-passage times and encounter rates are well known.
An image can be segmented using random walk segmentation by solving a sparse system of linear equations, Grady: “Random walks for image segmentation,” IEEE Trans. on Pattern Analysis and Machine Intelligence (PAMI), 28:1768-1783, 2006.
Grady also describes the incorporation of prior information into the random walk segmentation, Grady, “Multilabel random walker image segmentation using prior models,” in Proc. IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 2005. The prior information used is color prior probabilities in the form of a Gaussian mixture learned from training data.
However, the color prior probabilities do not always produce satisfactory result for the random walk segmentation, e.g., in the presence of image noise, background clutter and occlusions. Thus, it is desired to use the random walk segmentation with other types of prior information.